package com.leetcode.dynamicplan;

public class BackToOrigin {
    public static int backToOrigin(int n, int length){
//        n 走的步数，length 点的个数
        int[][] dp = new int[n + 1][length];
//        走0步到0这个位置，置位，表示从0出发
        dp[0][0] = 1;
        for(int i = 1; i < n + 1; i++){
            for(int j = 0; j < length; j++){
                dp[i][j] = dp[i - 1][(j - 1 + length) % length] + dp[i - 1][(j + 1) % length];
            }
        }
//        走n步到0这个位置
        return dp[n][0];
    }

    public static void main(String[] args) {
        int res = backToOrigin(2, 10);
        System.out.println(res);
    }
}
